COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input basic
C00003 00003	\problembegin 1. The camel of Khow\A arizm. (warmup problem, due October 5)
C00007 00004	\problembegin 2. Bit fiddling and image processing. (due October 19)
C00018 00005	\baselineskip14pt
C00024 00006	\problembegin 4. A language for Gosper arithmetic. (due November 16)
C00033 00007	\problembegin 5. Kriegspiel endgame. (due December 5)
C00037 ENDMK
C⊗;
\input basic
\def\problembegin #1. #2. (#3){\rjustline{CS204---Autumn 1978}\vskip3pt
\hjust to size{\bf Problem #1. \rm #2.\hfill(#3)}
\vskip 5pt\noindent\!}
\:w←cmsy8
\def\deg{↑{\hjust{\hskip-1pt\:w\char5}}}
\def\xskip{\hskip7pt plus3pt minus4pt}
\def\yskip{\penalty-50\vskip3pt plus3pt minus2pt}
\def\bslash{\char'477 }
\def\textindent#1{\noindent\hjust to 19pt{\hskip0ptplus1000ptminus1000pt#1 }\!}
\parindent19pt
\def\hang{\hangindent19pt}
\rm
\problembegin 1. The camel of Khow\A arizm. (warmup problem, due October 5)
Let $\phi = (1+\sqrt5\,)/2=1.$61803 39887 49894 84820 $\ldots$ be the
``golden ratio.''

A legendary camel in the ancient Persian valley of Khow\A arizm used to walk
around and around on a circular road that was
exactly one parathanha in circumference.
Every time this camel would travel a distance of precisely $\phi$ parathanh\ae,
it would deposit some beautiful dung that shone like gold. The golden dung
was, of course, bewitched; it was certain death to anyone who touched it
or disturbed it in any way. Thus, over the years a series of such deposits
continued to be built up along the road.

Everyone who passed that way noticed a strange thing---the golden cameldung
seemed to be almost equally spaced. One could practically use the heaps as
mileposts. In fact, at the time when there were $n$ deposits on the road,
the following condition was true (although only a few mathematicians knew it):
There was a point $x↓n$ on the road such that if you started at $x↓n$ you would
pass exactly one golden dung heap during the time it took to travel one $n$th
of a parathanha. Repeating this $n$ times until returning to $x↓n$, you would
see only one heap per segment of your tour. The mathematicians of that time
called this the ``$n$-fold cyclic dung distribution property.''

The magic camel never left the road, and it continued to make its enchanted deposits
for many years. Every time $n$ would increase by one, the $n$-fold cyclic
dung distribution property remained valid. But one year, just as a new deposit
was about to be made, a mysterious cloud appeared and  enveloped the poor beast;
and when the cloud moved away, the camel was gone. The spell was broken, and the
gold could now be freely taken.

One of the mathematicians had anticipated this, since he knew that the $n$-fold
cyclic dung distribution property would fail at the time of the next deposit.
This brilliant sorceror had made preparations for the fateful moment, and his
agents immediately pounced on the gold when the enchantment was lifted. He
became the richest man in the valley, so he gave up mathematics and was
assassinated two months later.

The problem is to determine $x↓n$ for $n=1$, 2, $\ldotss$; and to determine the
final value of $n$ when the camel vanished.

\vfill\eject
\problembegin 2. Bit fiddling and image processing. (due October 19)
In this problem we will be dealing with pictures represented on a discrete
raster. We have an $n\times n$ grid consisting of square ``pixels,'' each of
which is white or black. Using 0 to represent white and 1 to represent black,
we will be able to represent the picture compactly with 36 pixels per word
(on the AI Lab computer), and the computer's Boolean operations will facilitate
the manipulation of pictures. There are two parts to this problem: first to
``clean up'' a picture, and second to do edge-following that described the
boundaries of the ``objects'' in a cleaned-up picture.

\yskip\noindent
A. {\sl The cleaning-up phase} is intended to change stray black pixels to white
and vice versa, as well as to remove sharp turns of more than $90\deg$ at the
edges of black areas.

For purposes of discussion, a picture $P$ will be regarded as the set of all
black pixels in some image, and the complementary set $P↑-$ will be the set of
all white pixels. We define the {\sl closure} $P↑C$ of $P$ to be the smallest
picture containing $P$ such that every white pixel (i.e., every element of
$P↑{C-}$) is part of a $3\times3$ square of white pixels. A picture is {\sl
closed} if it is equal to its closure. The {\sl interior} $P↑O$ of $P$ is
defined to be the largest picture contained in $P$ such that every black pixel
is part of a $3\times3$ square of black pixels. A picture is {\sl open} if it is
equal to its interior.

Examples:\xskip (Imagine infinitely many white pixels surrounding these diagrams)
$$\hjust to size{$\hfill P=\vcenter{\halign{#\cr
1 1 0 0 1 1\cr
1 1 0 0 1 0\cr
0 1 1 1 1 0\cr
0 1 1 1 0 0\cr
0 0 1 0 0 0\cr}}\hfill P↑C=\vcenter{\halign{#\cr
1 1 1 1 1 1\cr
1 1 1 1 1 0\cr
0 1 1 1 1 0\cr
0 1 1 1 0 0\cr
0 0 1 0 0 0\cr}}\hfill P↑{CO}=\vcenter{\halign{#\cr
0 1 1 1 1 0\cr
0 1 1 1 1 0\cr
0 1 1 1 1 0\cr
0 1 1 1 0 0\cr
0 0 0 0 0 0\cr}}\hfill$}$$

The first subproblem is to replace a given picture $P$ by $P↑{CO}$, the interior
of its closure. We will say that a picture is {\sl clean} if it equals $P↑{CO}$
for some $P$. Write a program that finds $P↑{CO}$, given a $72\times72$ picture
$P$.

While solving this problem you may wish to develop a theory along the following
lines. Let us write
$$\def\\#1({\hjust{#1}(}\cpile{
x\prec y\qquad\hjust{if $\\row(x)≤\\row(y)≤\\row(x)+2$ and $\\col(x)≤\\col(y)≤
\\col(x)+2$;}\cr
x\succ y\qquad\hjust{if $\\row(x)-2≤\\row(y)≤\\row(x)$ and $\\col(x)-2≤\\col(y)
≤\\col(x)$.}\cr}$$
Furthermore we define
$$\cpile{P↑\prec=\leftset x\relv x\prec y \hjust{ for some $y$ in $P$}\rightset;\cr
P↑\succ=\leftset x\relv x\succ y \hjust{ for some $y$ in $P$}\rightset.\cr}$$

\eject
\noindent In these terms, prove or disprove the following statements:

\def\\{\noindent\hangindent 20pt}
\yskip\\(1) $P↑{-C-}=P↑O$.

\\(2) $P↑O$ is the union of all $3\times3$ square black pictures contained in $P$.

\\(3) $x\prec y$ if and only if $y\succ x$.

\\(4) $P↑\prec$ is open.

\\(5) $P↑O=P↑{-\prec{-}\succ}$.

\\(6) If $P$ is a picture such that every black pixel is included in a set of 3
consecutive black pixels in the same row and in a set of 3 consecutive black
pixels in the same column, then $P$ is open.

\\(7) If $P$ is a clean picture and if $x$, $y$, $z$ are three consecutive elements
of a row, where $x\in P$, $y\notin P$, and $z\in P$, then the pixels immediately
above and below $y$ are not in $P$.

\\(8) If $P$ is a clean picture and if $w$, $x$, $y$, $z$ are four consecutive
elements of a row, where $w\in P$, $x\notin P$, $y\notin P$, and $z\in P$, then
the pixels immediately above and below $x$ and $y$ are not in $P$.

\\(9) A clean picture is both open and closed.

\yskip\vskip 3pt
\noindent
B. {\sl The edge-tracing phase} is going to provide a description of a clean
picture that grows linearly (instead of quadratically) with the resolution of
the raster.

Let $P$ be a clean picture. We call the black pixel $x$ a {\sl boundary point}
of $P$ if at least one of $x$'s four neighbors (above, below, left, or right)
is white. The problem in this phase is to group the boundary points into
``closed cycles of king moves.'' In other words, if there are $m$ boundary
points, we want to arrange them into $p$ sequences
$$\lpile{x↓{11}, x↓{12}, \ldotss, x↓{1m↓1}\cr
\vdots\cr
x↓{p1}, x↓{p2}, \ldotss, x↓{pm↓p}\cr}$$
such that $m↓1+\cdots+m↓p=m$ and each $x↓{i(j+1)}$ is a king move away from
$x↓i$; also $x↓{i1}$ is a king move away from $x↓{im↓i}$. A king move is
a move one step up, down, left, right, or diagonally. In the example above,
all eleven of the boundary points belong to a single cycle
$$\baselineskip0pt\lineskip3pt\vjust{\halign{#⊗#⊗#⊗#\cr
$\bullet$ ⊗$\bullet$ ⊗$\bullet$ ⊗$\bullet$\cr
$\bullet$ ⊗⊗⊗$\bullet$\cr
$\bullet$ ⊗⊗⊗$\bullet$\cr
$\bullet$ ⊗$\bullet$ ⊗$\bullet$ \cr}}$$
of king moves, but in general we will have several cycles if there are several
disconnected areas of black, or if there are ``holes.''

The cycles of king moves can be still further refined, since it turns out that a
clean picture has cycles with the following property: After a diagonal move,
the path either stays in the same direction or branches $45\deg$ to the left
or right of its current direction. After a rectilinear move, the path either
stays moving in the same direction or branches $45\deg$ or $90\deg$ to the
left or right of its current direction. Thus we can encode each cycle as a
compact sequence of instruction pairs ``(number, turn)'', meaning to continue
in the same direction for the given number of steps and then to turn in the
specified way. When moving diagonally, the next turn will either be $L$ or $R$
($45\deg$ left or right); otherwise it will be either $LL$ or $LR$ or $RL$ or $RR$
($90\deg$ left, $45\deg$ left, $45\deg$ right, $90\deg$ right). We may assume
that the path begins in the upward direction in the leftmost column of the cycle;
thus, the example boundary above can be encoded by the sequence of king-move
instructions
$$(3,RR),\quad(3,RR),\quad(2,RL),\quad(1,R),\quad(2,RR).$$
(The final turn ``$RR$'' is redundant and could be omitted.)\xskip Together with
the coordinates of the starting point, this sequence of instructions
completely defines the cycle.

You are to write a program that produces such instruction sequences for the
boundary cycles of the clean $72\times72$ pictures produced by your first
program. You should also prove (informally) that your program will
handle all clean pictures.

\vfill\eject
\baselineskip14pt
\problembegin 3. Cubic spline drawing. (due November 2)
This problem arises in connection with drawing ``nice'' curves on a discrete
raster. We are given two cubic polynomials
$$\eqalign{x(t)⊗=x↓0+x↓1t+x↓2t↑2+x↓3t↑3,\cr
y(t)⊗=y↓0+y↓1t+y↓2t↑2+y↓3t↑3;\cr}$$and we wish to plot the curve $\biglp x(t),
y(t)\bigrp$ for $0≤t≤1$. But we are allowed to plot only integer points,
making king moves.

Here is the way Knuth solved this problem in the prototype version of his
``METAFONT'' system last year. First, he made the problem slightly more
general, namely to plot a set of curve segments $\biglp x(t),y(t)\bigrp$ for
$a↓i≤t≤b↓i$ and for $1≤i≤n$. Furthermore, it is possible to assume that $1\over2$
has been added to $x↓0$ and to $y↓0$, so that the closest integer point to
$\biglp x(t),y(t)\bigrp$ is $\biglp\lfloor x(t)\rfloor,\lfloor y(t)\rfloor\bigrp$.
Under these conditions, the algorithm repeatedly does this: Terminate if $n=0$.
Otherwise, if $x(t)$ is not monotonic between $t=a↓n$ and $t=b↓n$, find the
roots of its derivative $x↑\prime(t)$ and break the interval into two or three
intervals in which $x(t)$ is monotonic (increasing $n$ accordingly).
Similarly, the intervals are broken up even further, if necessary, so that both 
$x(t)$ and $y(t)$ are monotonic between $t=a↓n$ and $t=b↓n$. 
If now $\lfloor x(a↓n)\rfloor=\lfloor x(b↓n)
\rfloor$ or $\lfloor y(a↓n)\rfloor=\lfloor y(b↓n)\rfloor$, draw the
appropriate horizontal or vertical straight line (a rook move); decrease $n$ by 1.
Otherwise if $\lfloor x(a↓n)\rfloor=\lfloor x(b↓n)\rfloor\pm1$ and
$\lfloor y(a↓n)\rfloor=\lfloor y(b↓n)\rfloor\pm1$, make the appropriate diagonal
king move; decrease $n$ by 1. Otherwise replace the interval $[a↓n,b↓n]$ by
two intervals $[a↓n,{1\over2}(a↓n+b↓n)]$ and $[{1\over2}(a↓n+b↓n),b↓n]$;
increase $n$ by 1.

Knuth's ``binary splitting'' method seems somewhat elegant at first glance, but
the curves it draws are sometimes too skinny-looking and they occasionally
contain undesirable glitches near points where $t$ is a simple binary fraction.
Even when $x(t)$ and $y(t)$ are linear, the results are often very strange.
So the purpose of this problem is to help Knuth design a better routine for the
real METAFONT system. The new approach is intended to be faster and to give
better curves.

Here's the germ of an idea that should work better: By refining the intervals
a little more, we can ensure that $x(t)$ and $y(t)$ are not only monotonic in
each interval, their slope $y↑\prime(t)/x↑\prime(t)$ is never equal to $\pm1$
(unless the slope is constant in the interval). This means that the curves
in each interval will now be confined to one of eight ``octants''; by rotation
and/or reflection we can assume, for example, that $x(t)$ and $y(t)$ are
increasing and that $y(t)$ increases less rapidly than $x(t)$.\xskip (In other
words, $0≤y↑\prime(t)≤x↑\prime(t)$.)\xskip Now each move is either one rectilinear
step to the right, or one diagonal step up and right.

Find an efficient way to plot a given cubic spline curve $\biglp x(t),y(t)\bigrp$
for $0≤t≤1$, assuming that $0≤y↑\prime(t)≤x↑\prime(t)$ for $0≤t≤1$. Your algorithm
should decide as rapidly as possible whether or not each successive rightward move
should have slope 0 or 1. Then incorporate your method into an efficient subroutine
for the general problem.\xskip[{\sl Hint:} We would like to plot the
points $\biglp n,\lfloor y(t↓n)\rfloor\bigrp$, where $x(t↓n)=n$; but it is
probably not necessary to know the value of $t↓n$ very accurately.]

\vfill\eject
\baselineskip12pt
\problembegin 4. A language for Gosper arithmetic. (due November 16)
The main purpose of this problem is not to design a computer program---instead,
we will try to design a good {\sl programming language} of a new type (related
somewhat to the so-called ``data-flow'' languages being discussed nowadays
in connection with database systems). The semantics of a certain new
computational scheme will be sketched below; your task will be to suggest a
good interface by which a user will be able to use the scheme intelligently.

Here's the sketch: Every real number $x$ can be represented in a unique way as
a continued fraction
$$x↓0+{1\over\dispstyle{x↓1+{1\over x↓2+\cdots}}}$$
where $x↓0$ is an integer and $x↓1$, $x↓2$, $\ldots$ are infinitely many
positive integers; or perhaps $x↓k=∞$ for some $k$, in which case $x↓{k+1}$,
$x↓{k+2}$, $\ldots$ do not exist. For convenience in notation, we write $x=
x↓0+\bslash x↓1,x↓2,\ldotss\bslash$. The $x↓k$'s are called ``partial
quotients'' of $x$.

R. W. Gosper has developed a set of routines that do arithmetic directly on
the continued fraction representations of numbers. His routines have the neat
property that, when computing something like
$$z↓0+\bslash z↓1,z↓2,\ldotss\bslash\;\;←\;\;
\biglp x↓0+\bslash x↓1,x↓2,\ldotss\bslash\bigrp+
\biglp y↓0+\bslash y↓1,y↓2,\ldotss\bslash\bigrp,$$
they look at just enough of the $x↓i$ and $y↓j$ to determine $z↓k$ before
$z↓k$ is output, for $k=0$, 1, 2, $\ldotss\,$. Thus it is best to think of
his arithmetic procedures as {\sl coroutines} that produce one partial quotient
at a time when called on. Gosper's addition coroutine for $z←x+y$ is
effectively hooked up to the coroutine for $x$ and the coroutine for $y$; when
the $z$ coroutine is asked for a new partial quotient, it will call on the
$x$ and/or $y$ coroutines for more information, but only as much as necessary.

Actually {\sl every} numeric quantity in the system is a coroutine, at least at
the user's level of abstraction, and these coroutines are connected together
in a possibly gigantic network. There are no ordinary numbers, in the
old-fashioned static sense of some bit representation stored somewhere;
numeric quantities are totally dynamic. Nothing is ever computed ``to the end,''
the calculations just get more and more precise if this is called for.

When started or restarted, a coroutine for $x$ will sooner or later produce an
output that is either the next partial quotient for $x$ or it will produce
a coded message that means ``$x$ is indeterminate, but its next partial
quotient is anything between $a$ and $b$ inclusive, and don't ask me for
any more information.''\xskip This allows us to deal with inaccurate input data,
producing exactly as much output precision as is legitimate.

\eject\noindent Assume that the following types of coroutines are available:

\def\\{\hangindent 19pt after 0\noindent}
\yskip\\(1) Given two decimal numbers $x$ and $ε$, output the partial quotients for
a number that is indeterminate but between $x-ε$ and $x+ε$.

\\(2) Given two coroutines $x$ and $y$, output the partial quotients for $x+y$.

\\(3) Given two coroutines $x$ and $y$, output the partial quotients for $x-y$.

\\(4) Given two coroutines $x$ and $y$, output the partial quotients for $x\times
y$.

\\(5) Given two coroutines $x$ and $y$, output the partial quotients for $x/y$.

\\(6) Given a coroutine $x$, output the decimal digits of $x$.

\yskip\noindent Each of these coroutines will produce its outputs one at
a time, as called for. There is also a procedure that, given coroutines $x$ and
$y$, will produce one of four outputs: ``$x<y$'', ``$x=y$'', ``$x>y$'',
or ``indeterminate''.

All this sounds very nice, but there is a serious problem that has been glossed
over: In order to produce results in finite time, the coroutines sometimes have
to make guesses and retract bad guesses later. Furthermore the comparison
procedure might have to give a fifth output, ``I can't figure it out even
though I've checked lots of partial quotients of $x$ and $y$.''\xskip The
reason can be understood by considering the analogous situation where we are working
in the decimal number system instead of with continued fractions: After reading
finitely many digits of $\sqrt2=1.4142\ldotsm$, we will not be able to tell if the
square of this quantity is less than 2 or not, even though we know that it is
at least
$1.99999999999\ldotsm$ (say); we have to wait forever before we know even the
first digit of the product. When Gosper's routines appear to be computing too
long, he makes them produce a guessed-at result; if this turns out to be
wrong, they will later output a partial quotient that is zero or negative, in such
a way that the continued fraction will still evaluate to the correct final
value.

So that's the general idea. Our goal is to design a suitable user programming
language. To make the problem more explicit, you are asked to illustrate how
you would solve the following two problems using the language you design:

\yskip\\(a) Calculate a root of any given cubic equation.

\\(b) Solve a system of $n$ simultaneous linear equations (by some straightforward
scheme).

\yskip\noindent For each of these tasks, present a sample program in your
new language. Also give a brief description of the features of your language.\xskip
(But don't attempt to implement a compiler for it, wait until you take
CS240 or something.)

\vfill\eject
\problembegin 5. Kriegspiel endgame. (due December 5)

In this problem we are concerned with the game of chess where there is a white
king and white rook against a black king. An easy checkmate, you say; but there's
a twist: The white player does not know where the black king is.

The game starts with the white king and rook at their normal opening positions,
while the black king may be anywhere else (but not in check); White moves first.
Whenever White makes a move, he or she receives one of the following replies:

\yskip\hang\textindent{a)}Checkmate, you win.

\hang\textindent{b)}Stalemate, it's a draw.

\hang\textindent{c)}That move of yours is illegal because it puts your king next
to mine; try again.

\hang\textindent{d)}Your move put me in check, but it was not checkmate so I have
made my next move.

\hang\textindent{e)}Your move did not put me in check, and I have made my next
move.

\yskip\noindent It is possible for White to force checkmate in finitely many moves,
but the winning strategy is not easy to discover, so a good Black will usually
be able to escape.

Your problem is to design and program a Black strategy that plays 
``intelli\-gently'';
in particular, your program should be able to survive at least 100 moves against
two different White programs supplied by the grader.\xskip (These White programs
will, of course, be incorrect attacking strategies, typical of what a player
might try if he doesn't know the secret of winning.)\xskip You will not be able
to see the grader's second program until the final contest actually takes place
(nor will he look at your program); but the grader's first program will be
available to aid you in preliminary testing.

This game is different from true Kriegspiel in that Black does know the
positions of White's pieces. Furthermore, Black does not have to be committed
to particular king moves at each step, he or she is allowed to imagine being in
any set of possible positions consistent with what White has been told. After
seeing what White does, Black has the right to decide what the past history
actually was.

\vfill\eject